package com.skh.hash;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * created by skh on 2019/6/18
 * 三数之和
 */
public class ThreeSum {

	/*
	给定一个包含n个整数的数组，S中是否存在元素a、b、c使得a + b + c = 0?找出数组中所有唯一的三胞胎，它们的和为零。
	注意:
	三元组(a、b、c)中的元素必须按非降序排列。(即a≤b≤c)
	解决方案集不能包含重复的三元组。

    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)
	 */

	public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
		ArrayList<ArrayList<Integer>> result = new ArrayList<>();
		int length = num.length;
		Arrays.sort(num);
		int left, right, sum;

		for (int i = 0; i < length - 2;) {

			left = i + 1;
			right = length - 1;

			/**
			 * 固定一个数,从后面的数中选出两个数,因为数组是有序的,所以可以
			 * 用两个数组下标left和right,left指向当前元素的后一个位置,right指向最后一个位置
			 * 三个数相加的和等于0时,加入解集;
			 * 小于0时,把left往右边移动;
			 * 大于0时,把right往左边移动;
			 */
			while (left < right) {
				sum = num[left] + num[right] + num[i];
				if (sum == 0) {
					//加入解集
					ArrayList<Integer> tempList = new ArrayList<>();
					tempList.add(num[i]);
					tempList.add(num[left]);
					tempList.add(num[right]);
					result.add(tempList);

					left++;
					right--;

					// 从右向左找第一个与之前处理的数不同的数的下标
					while (left < right && num[right] == num[right + 1]) {
						right--;
					}

					// 从左向右找第一个与之前处理的数不同的数的下标
					while (left < right && num[left] == num[left - 1]) {
						left++;
					}

				} else if (sum > 0) {
					right--;
					// 从右向左找第一个与之前处理的数不同的数的下标
					while (left < right && num[right] == num[right + 1]) {
						right--;
					}
				} else {
					left++;
					// 从左向右找第一个与之前处理的数不同的数的下标
					while (left < right && num[left] == num[left - 1]) {
						left++;
					}
				}
			}

			// 指向下一个要处理的数
			i++;
			// 从左向右找第一个与之前处理的数不同的数的下标
			while (i < num.length - 2 && num[i] == num[i - 1]) {
				i++;
			}
		}


		return result;
	}

	public static void main(String[] args) {
		ThreeSum threeSum = new ThreeSum();
		int[] i = {-1,0 ,1, 2, - 1, - 4};
		ArrayList<ArrayList<Integer>> arrayLists = threeSum.threeSum(i);
		System.out.println("arrayLists = " + arrayLists);
	}

}
